package recursion

func GetWinSum(cards []int) int {
	return GetWinSumProcess(cards, 0, len(cards)-1)
}

func GetWinSumProcess(cards []int, L, R int) int {
	p1 := First(cards, L, R)
	p2 := Second(cards, L, R)
	return max(p1, p2)
}

func First(cards []int, L, R int) int {
	if L == R {
		return cards[L]
	}
	return Max(
			Second(cards, L+1, R) + cards[L],
			Second(cards, L, R-1) + cards[R],
		)
}

func Second(cards []int, L, R int) int {
	if L==R {
		return 0
	}
	return  Min(
		First(cards, L+1, R),
		First(cards, L, R-1),
	)
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func Min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func GetWinSumDp(cards []int) int {
	l := len(cards)
	f := make([][]int, l)
	s := make([][]int, l)
	// 初始化
	for i:=0; i<l; i++ {
		f[i] = make([]int, l)
		s[i] = make([]int, l)
		f[i][i] = cards[i]
	}

	// 推出f和s表
	for i:=0; i<l; i++{
		L := 0
		R := i+1
		for L < l && R < l {
			f[L][R] = Max(s[L+1][R]+cards[L], s[L][R-1]+cards[R])
			s[L][R] = Min(f[L+1][R], f[L][R-1])
			L++
			R++
		}
	}
	return Max(f[0][l-1], s[0][l-1])
}